0994. 腐烂的橘子【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 多源 BFS

1. 📝 题目描述

• leetcode

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

• 值 0 代表空单元格；
• 值 1 代表新鲜橘子；
• 值 2 代表腐烂的橘子。

每分钟，腐烂的橘子周围 4 个方向上相邻的新鲜橘子都会腐烂。

返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。

---

示例 1：

输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
输出：4

---

示例 2：

输入：grid = [[2,1,1],[0,1,1],[1,0,1]]
输出：-1

解释：
左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个方向上。

---

示例 3：

输入：grid = [[0,2]]
输出：0

解释：
因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0。

---

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 10
• grid[i][j] 仅为 0、1 或 2

2. 🎯 s.1 - 多源 BFS

js

/**
 * @param {number[][]} grid
 * @return {number}
 */
var orangesRotting = function (grid) {
  const m = grid.length
  const n = grid[0].length
  const queue = []
  let fresh = 0 // 新鲜橘子数量

  // 统计新鲜橘子数量，将所有腐烂橘子加入队列
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === 1) {
        fresh++
      } else if (grid[i][j] === 2) {
        queue.push([i, j])
      }
    }
  }

  // 如果没有新鲜橘子，直接返回 0
  if (fresh === 0) return 0

  const directions = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0],
  ]
  let minutes = 0

  // BFS 多源扩散
  while (queue.length > 0) {
    const size = queue.length
    let hasRotten = false

    for (let i = 0; i < size; i++) {
      const [x, y] = queue.shift()

      for (const [dx, dy] of directions) {
        const nx = x + dx
        const ny = y + dy

        // 检查边界和是否为新鲜橘子
        if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] === 1) {
          grid[nx][ny] = 2 // 腐烂
          queue.push([nx, ny])
          fresh--
          hasRotten = true
        }
      }
    }

    if (hasRotten) minutes++
  }

  return fresh === 0 ? minutes : -1
}

• 时间复杂度：$O(m\times n)$，其中 m 和 n 分别是网格的行数和列数，每个单元格最多被访问一次
• 空间复杂度：$O(m\times n)$，队列中最多存储所有橘子的位置

算法思路：

• 初始化：遍历网格统计新鲜橘子数量，将所有腐烂橘子的位置加入队列作为多源起点
• 特殊情况：如果初始时没有新鲜橘子，直接返回 0
• BFS 扩散：每一轮处理队列中的所有腐烂橘子，向四个方向扩散腐烂相邻的新鲜橘子
• 时间统计：每完成一轮扩散且有新橘子腐烂时，分钟数加 1
• 结果判断：如果最终还有新鲜橘子剩余，返回 -1，否则返回经过的分钟数